package SubjectTree.Four;

import java.util.Deque;
import java.util.LinkedList;

import Utility.TreeNode;

public class SearchBST {

/**
 * 难度：简单
 * 
 * 700. 二叉搜索树中的搜索
 * 	给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
 * 	
 * 例如，
 * 	给定二叉搜索树:
 * 	        4
 * 	       / \
 * 	      2   7
 * 	     / \
 * 	    1   3
 * 	和值: 2
 * 	你应该返回如下子树:
 * 	      2     
 * 	     / \   
 * 	    1   3
 * 	在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		SearchBST sbst = new SearchBST();
		System.out.println(sbst.searchBST_1(TreeNode.MkTree("[4,2,7,1,3]"), 2));
	}
	//自己写(前序遍历)
	public TreeNode searchBST(TreeNode root, int val) {
		if(root==null)return null;
		Deque<TreeNode> deque = new LinkedList<>();
		while(!deque.isEmpty()||root!=null) {
			while(root!=null) {
				if(root.val == val)return root;
				deque.push(root);
				root = root.left;
			}
			root = deque.pop();
			root = root.right;
		}
		return null;
    }
	//自己写(递归)
	public TreeNode searchBST_1(TreeNode root, int val) {
		if(root==null)return null;
		if(root.val==val) return root;
		
		TreeNode node = new TreeNode(0);
		
		node.left = searchBST_1(root.left, val);
		node.right = searchBST_1(root.right, val);
		
		if(node.left!=null&&node.left.val == val) {
			return node.left;
		}else if(node.right!=null&&node.right.val == val){
			return node.right;
		}else {
			return null;
		}
    }
	//方法一：递归
	public TreeNode searchBST1(TreeNode root, int val) {
		if (root == null || val == root.val) return root;

		return val < root.val ? searchBST1(root.left, val) : searchBST1(root.right, val);
	}
	//方法二：迭代
	public TreeNode searchBST2(TreeNode root, int val) {
	    while (root != null && val != root.val)
	      root = val < root.val ? root.left : root.right;
	    return root;
	}
}
